structure Reachingdefs :
sig

    datatype rdgraph= RDGRAPH of {ins: BitArray.array array, out : BitArray.array array, defs : Graph.node list Temp.Table.table, nodestm : int Graph.Table.table, use : Graph.node list Temp.Table.table, nodes : Graph.node list, nodetable : int Graph.Table.table}
   
    val reachingdefinitionsGraph : (GenKillgraph.gkgraph * Graph.node list) -> rdgraph
					      
end =

struct 

    structure E = ErrorMsg
    structure G = Graph
    structure GB = Graph.Table
    structure M = Temp
    structure MB = M.Table
    structure U = UnparseAbsyn
    structure GK = GenKillgraph
   
    structure ARR = Array
    structure BITS = BitArray
    structure LST = List
    structure OPT = Option
    structure VEC = Vector
		    
    datatype rdgraph = RDGRAPH of {ins: BITS.array array, out : BITS.array array, defs : G.node list M.Table.table, nodestm : int GB.table , use : G.node list M.Table.table , nodes : G.node list, nodetable :  int GB.table }
    
    fun reachingdefinitionsGraph (GK.GKGRAPH {control, gen,kill,def,nodestm, use}, fnodes) =
	let 
	    val ins = ref GB.empty
	    val out = ref GB.empty
            val (fnodeTable, fnodeCount) = foldl (fn (n, (ntable, next)) => (GB.enter (ntable, n, next),
									     next+1))
						 (GB.empty, 0)
						 fnodes
	    fun fnodeIndex n = OPT.getOpt (GB.look (fnodeTable, n), ~1) (* error if  then not found *)
	
	    (* and a vector containing a list of the predessor node indicies for each node *)
	    val predIndex = VEC.fromList (map (fn n => map fnodeIndex (G.pred n))
					      fnodes)

	   (*  val defCount = length ( GB.keys (gen)) *)
            val inn  = ARR.array (fnodeCount, BITS.bits (fnodeCount, []))
	    val outn = ARR.array (fnodeCount, BITS.bits (fnodeCount, []))
	    fun nodeindex node = let val i = OPT.getOpt (GB.look (fnodeTable,node),0)
				 in i
				 end
	    fun nodes2bits nodes = BITS.bits (fnodeCount, map nodeindex nodes)
           
            
	    fun tab2bits tab = VEC.fromList (map (fn n => nodes2bits (OPT.getOpt (GB.look (tab,n),[]))) fnodes)
           
	    val killn = tab2bits kill
	    val genn = tab2bits gen
	    val change = ref true

	in  
           ( let val n = ref 0
           (* initialize  out to gen *)
	    in ( 
                (* big loop *)
	       while (!change) do
		   ( 
		    change := false;
		    (*inner loop*)
		    while (!n < fnodeCount)  do
			  (
			   let val inn' = ARR.sub (inn, !n)
			       val outn' = ARR.sub (outn, !n)
			   in
			       (* generarting in list *)
			       ( app (fn s => ARR.update (inn, !n, BITS.orb (ARR.sub (inn, !n),
									      ARR.sub (outn, s),
									      fnodeCount)))
				     (VEC.sub (predIndex, !n))
			       (* generarting out list *)
			      ;ARR.update (outn , !n, BITS.orb (VEC.sub (genn, !n), BITS.andb (ARR.sub (inn, !n), VEC.sub (killn, !n), fnodeCount), fnodeCount))
			      ; if (not (BITS.equal (inn', ARR.sub (inn, !n))
					  andalso BITS.equal (outn', ARR.sub (outn, !n))))
				 then change := true
				 else ()
			       )
			   end
	                  ;n:= !n +1
			   
                          )
		   )
	       )
	    end 
            ; RDGRAPH  {ins= inn, out = outn, defs = def, nodestm = nodestm, use = use , nodes = fnodes , nodetable = fnodeTable}
	     )
   end (* reachingdefinitionsGraph end *)

   
end (* struct end *)
